\documentclass{beamer}
\usepackage{beamerthemesplit,graphicx}
\usepackage{listings}
\usepackage{subfigure}
\usetheme{CambridgeUS}
\setbeamercovered{transparent}
\title{Turtlebot (Tiny)SLAM }
\author{Cristian Calmuschi\\Andreas Hamacher\\Gergely Kosztol\'{a}nyi\\Yannick Thimister}
\date{\today}
\renewcommand{\thefootnote}{}

\setbeamertemplate{footline}{
  \leavevmode%
  \hbox{%
  \begin{beamercolorbox}[wd=.333333\paperwidth,ht=2.25ex,dp=1ex,center]{author in head/foot}%
    \usebeamerfont{author in head/foot} Group 3
  \end{beamercolorbox}%
  \begin{beamercolorbox}[wd=.333333\paperwidth,ht=2.25ex,dp=1ex,center]{title in head/foot}%
    \usebeamerfont{title in head/foot}\insertshorttitle
  \end{beamercolorbox}%
  \begin{beamercolorbox}[wd=.333333\paperwidth,ht=2.25ex,dp=1ex,right]{date in head/foot}%
    \usebeamerfont{date in head/foot}\insertshortdate{}\hspace*{2em}
    \insertframenumber{} / \inserttotalframenumber\hspace*{2ex} 
  \end{beamercolorbox}}%
  \vskip0pt%
}


\begin{document}

\frame{
	\titlepage
}

\frame{
\frametitle{Introduction}
\begin{figure}
\centering
	\includegraphics[width=0.3\textwidth]{swarmlab_map}
	\hspace{10pt}
	\includegraphics[width=0.3\textwidth]{tiny_2_30min}
\end{figure}
}

\section[Outline]{}
\frame{
\frametitle{Outline}
\tableofcontents
}


\section{Autonomous Exploration}

\frame{
\frametitle{Exploration}
\begin{figure}
\centering
\includegraphics[width=0.6\textwidth]{gregslide} 
\end{figure}
}

\frame{
\frametitle{Frontier-based Exploration}
\begin{itemize}
	\item Frontier Detection
	\begin{itemize}
		\item Basic Edge Detection
	\end{itemize}
	\item Frontier Selection
\end{itemize}
\begin{itemize}
	\item Ranking cells
		\begin{itemize}
			\item Trivial approach$\colon$ raycasting from every cell
			\begin{itemize}
				\item Inefficient
			\end{itemize}
			\item Our approach$\colon$ makes use of reciprocity of light
			\begin{itemize}
				\item Shading Algorithm
			\end{itemize}
		\end{itemize}

\end{itemize}
}


\frame{
\frametitle{Frontier Selection}
\begin{itemize}
	\item Simple approach 1$\colon$ selecting the cell with highest value
	\begin{itemize}
		\item Inefficient
	\end{itemize}
	\item Simple approach 2$\colon$ evaluating every cell based on value and distance
	\begin{itemize}
		\item Inefficient
	\end{itemize}
\end{itemize}

\begin{itemize}
	\item Our approach:

	\begin{itemize}
		\item Use local maximums as candidates
		\item Evaluate them based on their value and distance
		\item Detects good cells all over the map
		\item Uses few cells
	\end{itemize}
\end{itemize}
}


\section{Navigation}
\frame{
\frametitle{Navigation}
Common approaches:
\begin{itemize}
	\item Grid-based A* / Dijsktra (for multiple destinations)
	\begin{itemize}
		\item Restricted to 45 degree angles
		\item Smoothing required (Theta*)
	\end{itemize}
	\item Visibility graph
	\begin{itemize}
		\item Very large graph
		\item Physical constraints introduce costly calculations
	\end{itemize}
\end{itemize}
}

\frame{
\frametitle{Navigation}
Own approach:
\begin{itemize}
	\item Semi-Topological
	\item Navigational aids placed onto the edges of a Voronoi-graph
	\item Aids used in an A* / Dijkstra search
	\item Smaller graph than a visibility graph, yet similar results
\end{itemize}
}

\section{TinySLAM} 
\begin{frame}
\frametitle{Idea of  TinySLAM} 
%- implemented basically in two days.  
%- explain original purpose. 
%- particly or standalone possible
%-- standalone simple MC scan matching least squares error
%-- particle distance scan to map. 
%-- odometry directly corrected in standalone version by a comparison of scan and known map.
%- mapping: bresenham line approximation of scan front 
%- reduced mapping resolution 1cm
%--subpixel accuracy because a scan consists of a line/several points. 

%- suited for fast moving robots with good odometry but average laser
%- robust algorithm, 
%- low accuracy  
%- computing efficient
\begin{itemize}
\item Few lines of code and very easy to understand
\item Implemented basically in two days
\item Low mapping resolution ca. 1 cm
\item Bresenham line approximation of scan front for mapping
\item Computational efficient
\item MC based scan matching
\item Local odometry error correction
\item Optimized for fast moving robots
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{TinySLAM Mapping} 
%\includegraphics[scale=1\paperwidth]{movement_error.jpg}
\begin{center}
\includegraphics[width=0.7\textwidth]{mapping_a.jpg} 
\end{center}
\end{frame}

\begin{frame}
\frametitle{TinySLAM scan-to-map} 
%\includegraphics[scale=1\paperwidth]{movement_error.jpg}
\begin{center}
\includegraphics[width=0.7\textwidth]{mapping_b.jpg} 
\end{center}
\begin{itemize}
\item Problem: Noise generates fake walls with low probability
\item Problem: Unoccupied Areas behind walls
\end{itemize}
\end{frame}


\begin{frame}
\frametitle{ Particle-Tiny-SLAM  } 
\begin{center}
\includegraphics[width=0.7\textwidth]{mapping_c.jpg} 
\end{center}
\begin{itemize}
\item Accuracy depends on the number of gridcells per line
\item Subpixel accuracy
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{TinySLAM and Movementspeed} 
\begin{center}
\includegraphics[width=0.7\textwidth]{movement_error.jpg} 
\end{center}
\end{frame}

\begin{frame}
\frametitle{SLAM Comparison}
\begin{center}
\begin{tabular}{| l || c | c | c |}
  \hline                        
   & TinySLAM & GraphSLAM & Particle \\
  \hline \hline                       
  accuracy & - & + & + \\
  \hline   
  complexity & + & - & 0 \\
  \hline   
  simplicity & + & - & + \\
  \hline  
\end{tabular}
\end{center}
\end{frame}

\section{Experiments and Results}

\frame{
\frametitle{Experimental Setup}
\begin{columns} 
    \column[h]{.50\textwidth} 
    {
   	\begin{itemize}

	\item Draw qualitative conclusions from saved maps
	\item gMapping vs. TinySLAM vs. Original Map
	\item Save maps at 5, 15 and 30 minutes
	\begin{itemize}
		\item Evaluate exploration efficiency
		\item Compare progress
	\end{itemize}
	\item 2 different starting points
	\begin{itemize}
		\item narrow area
		\item open area
	\end{itemize}
	\end{itemize}
    }
    	\column[h]{.50\textwidth} 
	\hspace{20pt}
   	\includegraphics[width=0.6\textwidth]{swarmlab_map2} 
  \end{columns}   	
}


\frame{
\frametitle{Narrow start after 5 minutes}
\begin{figure}
	\includegraphics[width=0.3\textwidth]{gmap_narrow_5}
	\hspace{20pt}
	\includegraphics[width=0.3\textwidth]{tiny_narrow_5}
\end{figure}
\begin{itemize}
	\item gMapping is more accurate
	\item Double walls
	\item Overshooting
\end{itemize}
}

\frame{
\frametitle{Open start after 30 minutes}
\begin{figure}
	\includegraphics[width=0.2\textwidth]{swarmlab_map}
	\hspace{20pt}
	\includegraphics[width=0.2\textwidth]{tiny_open_30}
\end{figure}
\begin{itemize}
	\item TinySLAM  overcomes problems over time
	\begin{itemize}
		\item Fake walls removed
		\item Overshooting creates fake frontiers, but cause no problem
	\end{itemize}
	\item Artifacts impact navigation
\end{itemize}
}

\frame{
\frametitle{Narrow vs. Open starting area}
\begin{figure}
	\includegraphics[width=0.3\textwidth]{tiny_narrow_30}
	\hspace{20pt}
	\includegraphics[width=0.3\textwidth]{tiny_open_30}
\end{figure}
\begin{itemize}
	\item Narrow passageways decrease rate of exploration
\end{itemize}
}



\section{Conclusions}

\frame{

\frametitle{Conclusions}

\begin{itemize}

	\item SLAM is handling uncertainty still noise filtering improves results
	\begin{itemize}
		\item Sensor hardware dependency
	\end{itemize}


	\item Trade-offs between TinySLAM and GraphSLAM

	\item Shortcomings of ROS navigation solved with own implementation

\end{itemize}

}

\section{Future Research}

\frame{

\frametitle{Future Research}

\begin{itemize}

	\item Reduce overall computing time

	\item Extend with loop closure

\end{itemize}

}

\section{Demonstration}

\frame{

\frametitle{Demonstration}

}




\section{Questions}
\frame{
\frametitle{Thanks and Questions?}
\begin{itemize}
	\item Thank you for your attention
	\item Questions?
\end{itemize}
}

\end{document}